The present invention relates to methods and apparatus for producing a halftone image including embedded data, such as data indicating the origin of the image. In particular the data is embedded such that it can be revealed by comparison of the halftone image with a second halftone image.
Nowadays, digital images can be distributed easily through the Internet and the Web. As a side effect, the problems of copyright infringement and authentication are growing rapidly with the ease of distribution. One possible solution is to hide within the images xe2x80x9cwatermarkingxe2x80x9d data such as identity of the company which produced the image, the owner of the image, its creation date and time, for copyright protection and authentication purposes. The embedded watermarking data should not be visible.
Halftoning is a method widely used to transform multi-tone images (typically xe2x80x9cgrey-scalexe2x80x9d images with 256 levels at each pixel, although in this document the term multi-tone is used to imply merely that there are at least 3 levels, or more preferably at least 10 levels) into a xe2x80x9chalftonexe2x80x9d image having only two tone colors (i.e. 2 levels) at each pixel. Such methods are used widely, for example in computer printers and for publishing newspapers, magazines and books. From a distance, halftoned images resemble images with multi-tones. The two most commonly used halftoning techniques are known as xe2x80x9cordered ditheringxe2x80x9d (see B. E. Bayers, xe2x80x9cAn optimum method for two level rendition of continuous tone picturesxe2x80x9d, Proc. of IEEE Int. Communication Conf., pp2611-2615, 1973) and xe2x80x9cerror diffusionxe2x80x9d (R. W. Floyd, L. Steinberg, xe2x80x9cAn adaptive algorithm for spatial greyscalexe2x80x9d, Proc. SID, pp 75-77, 1976). Typically, the second of the two techniques produces half-tone images of higher quality.
Ordered dithering is a computationally simple and effective halftoning method. It employs a xe2x80x9cscreenxe2x80x9d having at each pixel a pseudo-random value, and sets the tone of the halftone value at each pixel according to whether the grey-tone value at that pixel is higher or lower than the pseudo-random value. With ordered dithering, the average local intensity within a screen region of the generated halftone image corresponds approximately to that of the original grey-tone image. Unfortunately, the technique introduces a high level of undesirable noise and gives low image quality.
Error diffusion is a more advanced technique usually used in certain printers. It is more complicated than ordered dithering, but it can generate halftone images with higher visual quality. It is a single pass algorithm (i.e. pixels are processed in a single sweep across the image. For example, the method may process the rows one-by-one from top to bottom of the image, and, for each row, process the pixels one-by-one along the row, e.g. left to right; clearly these orders may be varied, e.g. by processing successive columns rather than rows). In error diffusion, the halftoning output is obtained by comparing the grey-tone value of each given pixel with a fixed threshold, and generating a halftone value according to the result of the comparison. The halftoning error generated in this way (for example, in the case of a pixel having a grey-tone value below the threshold, the halftoning error for that pixel is the grey-tone value itself) is fed forward to its adjacent neighbors, specifically to pixels which are later in the single pass across the image performed by the algorithm. For those adjacent pixels the halftone values are calculated by comparing the threshold with a sum of the grey-tone values for those pixels plus a fraction of the error value fed forward. In other words, each image pixel effectively has an adaptive threshold. The error feedback helps to make the local average intensity of the halftone image approximately equal to the original multi-tone image (neglecting any trivial constant factor arising because from the definition of the two possible halftone values (e.g. either 0 or 255 whereas the multi-tone values are in the range 0 to 255)). An essential component of error diffusion is its error feedback kernel, which determines the proportion of the error fed from a given pixel to each of its adjacent pixels. Different kernels can have quite different behaviour. Two commonly used error feedback kernels are the Jarvis kernel and the Steinberg kernel shown in Tables 1 and 2 respectively.
The Jarvis kernel has a large support and tends to give halftone images with high contrast and coarse texture. The Steinberg kernel has smaller support and gives halftone images with fine texture and good contrast. In each case, each element of tables 1 and 2 refers to a respective pixel. The element with an entry marked xe2x80x9cxxe2x80x9d refers to the pixel currently being processed. Each numerical entry shows the weighting on the pixel presently being processed from the error caused by halftoning in the pixel with the numerical entry.
There have been quite a number of watermarking methods designed for natural grey scale images. However, few, if any, of the algorithms can be applied to halftone images. This is because halftone images have only 2 tones and have a large amount of high frequency noise resulting in little intensity redundancy. Few image processing operations can be performed on halftone images without creating serious perceptual artifacts.
The present inventors have recently proposed a technique in which data is hidden in a half-tone image at individual data storage pixels chosen using a pseudo-random number generator. At each data storage pixel, the halftone value is fixed at a value determined by the data to be hidden.
In a first case, the data is hidden within an existing halftone image. Hiding the data requires reversing the tone value at about half of the data storage pixels. For such pixels, the tone value of one of the adjacent pixels is also reversedxe2x80x94to maintain the local average intensity.
In a second case, the data is hidden while the half-tone image is generated from a grey-scale image by error diffusion. In the case of the data storage pixels, the halftone value is determined by the data to be hidden. The error caused by doing this (i.e. the difference between the grey-tone value of the original image for that pixel and the halftone value determined by the data to be hidden) is fed to adjacent pixels, as in error diffusion. However, this error may be fed not only to pixels which are ahead in the sweep across the image, but also to pixels which are earlier in the single pass across the image (i.e. the kernel is xe2x80x9cnon-causalxe2x80x9d).
In both of these cases, the hidden data is regenerated by using the same pseudo-random algorithm to determine the data storage pixels. This algorithm is very effective in hiding a large amount of data with very low degradation of the half-tone image (e.g. 4096 bits of hidden data in a 512xc3x97512 image).
In certain applications, however, it is preferable for the data to be hidden so that it can be extracted more rapidly from the half-tone image. For example, it would be useful if the data could be extracted from a digitised half-tone image by a method which does not require knowledge or use of a pseudo-random algorithm. In some applications it would be advantageous if the method can be performed directly on a printed image without the need for scanning it.
U.S. Pat. Nos. 5,709,703, 5,734,752, 5,488,664, 5,315,098 and 5,296,559 all relate to methods of generating a halftone image including hidden data by ordered dithering. Generally speaking, they transform a multi-tone image into two halftone images by ordered dithering using respective screens. A first screen is composed of random grey-tone values at each pixel. A second screen is composed of random grey-tone values correlated with the first screen in some portions, and grey-tone values uncorrelated with the first screen in other portions. When the two halftone images are superimposed, the portions in which the two screens are correlated have a different average intensity from portions in which the screens are uncorrelated, and in this way the correlated portions are revealed. The locations of these correlated portions can be used to encode the hidden data.
A major disadvantage of such techniques, however, is that since they employ ordered dithering, the quality of the halftone images is low.
The present invention seeks to provide a new and useful way of generating a halftone image incorporating hidden data.
In general terms the invention proposes that error diffusion is used to generate two halftone images from a single multi-tone image. The two halftone images are identical in one or more portions (xe2x80x9cbackground portionsxe2x80x9d), but only statistically correlated in one or more other portions (xe2x80x9cforeground portionsxe2x80x9d). The set of data to be hidden determines the partition of the pixel array into the background portions and foreground portions (i.e. the locations of the centres of the portions, and the shapes of the portions). The two sorts of portions can be revealed by comparison of the images. In fact, as explained below, the locations and shapes of the portions are normally visible when the two halftone images are superimposed.
Preferably, the respective local average intensities of the two halftone images are approximately the same (possibly neglecting a trivial constant factor) throughout the images (both being equal to the local average intensity of the original multi-tone image, for example), but the xe2x80x9cphasexe2x80x9d of the two half-tone images is different in the foreground portion(s) of the images.
One way for this to be realised is for a first of the two halftone images to be generated by a conventional error diffusion process. The background portions of the second of the two halftone images may be generated by copying the first halftone image. The foreground portions of the second image may be generated by an error diffusion process, in which the error fed from the background portions of the second image is different from the error fed from the corresponding portions during the creation of the first image.
A further possibility within the scope of the invention is to use an error diffusion process to generate a third halftone image, hiding a second set of hidden data. In other words, the second hidden data would define a second partition of the array into a foreground portion and a background portion. The third halftone image would be identical to the first halftone image in the second background portion, and merely correlated with it in the second foreground portion. Thus, if the second image and the third image are compared, they only match in those portions of the images which are in the background according to both sets of hidden data; the portions of the second and third images which differ, represent areas which are in one or other of the two foreground regions. Such areas may be visible if the second and third areas are superimposed.
Preferably, the two sets of data hidden in the respective images are complementary, in the sense that the two sets of data encode information (a third data set) which cannot be derived from either of the two sets of hidden data alone. For example, this further information may be encoded as a correlation between the first and second data sets.